#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//#include<math.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int arr[2000] = { 0 };
//    int i = 0;
//    int max = sqrt(arr[0]);
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &arr[i]);
//        if (sqrt(arr[i] > max))
//        {
//            max = arr[i];
//        }
//    }
//    printf("%d", max);
//    return 0;
//}
//#include<stdio.h>
//long long  Find(long long n)
//{
//    if (n == 0)
//        return 0;
//    if (n == 1)
//        return 1;
//    else
//        return Find(n / 2) + Find(n % 2);
//}
//long long Fib(long long n)
//{
//    long long i = 0;
//    while (1)
//    {
//        if (Find(i) == Find(n))
//        {
//            break;
//        }
//        else
//        {
//            i++;
//        }
//    }
//    return i;
//}
//int main()
//{
//
//    long long k = 0;
//    scanf("%lld", &k);
//    long long i = 0;
//    long long arr[100] = { 0 };
//    for (i = 0; i < k; i++)
//    {
//        scanf("%lld", &arr[i]);
//    }
//    for (i = 0; i < k; i++)
//    {
//        long long ret1 = Find(arr[i]);
//        long long num1 = Fib(arr[i]);
//        printf("%lld %lld", ret1, num1);
//        printf("\n");
//    }
////    return 0;
////}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	char arr[10] = { 0 };
//	getchar();
//	gets(arr);
//	return 0;
//}

//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	char arr[10] = { 0 };
//	getchar();
//	fgets(arr, 10, stdin);
//	return 0;
//
//}

//#include <stdio.h>
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	char arr[50] = { 0 };
//	getchar();
//	char a = getchar();
//	getchar();
//	char b = getchar();
//	getchar();
//	char c = getchar();
//	getchar();
//	char d = getchar();
//	getchar();
//	fgets(arr, 50, stdin);
//    int i = 0;
//    while (arr[i] != '\0')
//    {
//        if (arr[i] == a)
//        {
//            arr[i] = b;
//        }
//        if (arr[i] == c)
//        {
//            arr[i] = d;
//        }
//        i++;
//    }
//    while (arr[i] != '\0')
//    {
//        if (arr[i] == a)
//        {
//            arr[i] = b;
//        }
//        if (arr[i] == c)
//        {
//            arr[i] = d;
//        }
//        i++;
//    }
//    printf("%s", arr);
//	return 0;
//}
//#include <stdio.h>
//int Fib(int n)
//{
//    if (n > 9)
//        return Fib(n / 10) + pow(n % 10, 4);
//    else
//        return pow(n, 4);
//}
//int main()
//{
//    int n = 0;
//    int m = 0;
//    scanf("%d %d", &n, &m);
//    int i = 0;
//    for (i = n; i <= m; i++)
//    {
//        if (i == Fib(i))
//        {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}
//#include <stdio.h>
//int Fib(int n)
//{
//    int i = 0;
//    int count = 0;
//    for (i = 0; i < 32; i++)
//    {
//        if (((n >> i) & 1) == 1)
//            count++;
//    }
//    int sum = 32 - count;
//    if ((count % 2 == 0) && (sum % 2 != 0))
//    {
//        return 1;
//    }
//    else if ((count % 2 != 0) && (sum % 2 == 0))
//    {
//        return 0;
//    }
//    else if ((count % 2 == 0) && (sum % 2 == 0))
//    {
//        return 2;
//    }
//    else
//    {
//        return 3;
//    }
//}
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int i = 0;
//    int arr[100] = { 0 };
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &arr[i]);
//    }
//    for (i = 0; i < n; i++)
//    {
//        int ret = Fib(arr[i]);
//        if (ret == 1)
//        {
//            printf("%d ", 1);
//        }
//        else if (ret == 0)
//        {
//            printf("%d ", 0);
//        }
//        else if (ret == 2)
//        {
//            printf("%d ", 10);
//        }
//        else
//        {
//            printf("%d ", 100);
//        }
//    }
//    return 0;
//}
//
//
//#include<stdio.h>
//int two_num(int x) {
//    int count1 = 0, count0 = 0;
//    while (x > 0) {
//        if (x % 2 == 0)
//            count0++;
//        else
//            count1++;
//        x /= 2;
//    }
//    if (count0 % 2 == 0 && count1 % 2 == 0) {
//        printf("10 ");
//    }
//    else if (count0 % 2 == 0 && count1 % 2 != 0) {
//        printf("0 ");
//    }
//    else if (count1 % 2 == 0 && count0 % 2 != 0) {
//        printf("1 ");
//    }
//    else {
//        printf("100 ");
//    }
//    return 0;
//}
//int main() {
//    int n = 0, x = 0;
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++) {
//        scanf("%d", &x);
//        two_num(x);
//    }
//    return 0;
//}